/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	return dfs(lists, 0, len(lists)-1)
}
func dfs(lists []*ListNode, left, right int) *ListNode {
	if left == right {
		return lists[left]
	}
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	list1 := dfs(lists, left, mid)
	list2 := dfs(lists, mid+1, right)
	return mergeTwoLists(list1, list2)
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	protect := &ListNode{}
	p := protect
	for list1 != nil || list2 != nil {
		if list1 != nil && list2 != nil {
			if list1.Val < list2.Val {
				p.Next = list1
				list1 = list1.Next
			} else {
				p.Next = list2
				list2 = list2.Next
			}
			p = p.Next
		} else if list1 != nil {
			p.Next = list1
			break
		} else {
			p.Next = list2
			break
		}
	}
	return protect.Next
}
